2707. [SDOI2012]走迷宫

发表于

闲扯

概率期望好题。

题面

#2707. [SDOI2012]走迷宫

Solution

设 $E(u)$ 表示从 $u$ 出发，到达 $t$ 的期望步数。

显然，我们有 $E(u)=\sum_{(u,v)\in E}\frac{E(v)+1}{deg_u}$ 。

对于不同 $SCC$ 里面的点，我们显然可以直接转移。

对于同一个 $SCC$ 里面的点，它们的转移成环，用高斯消元即可。

需要注意的是，在之前进行拓扑排序时，我们可能已经计算了一些 $E(u)$ ，我们直接将它们看做常数项即可。（高消里面只需要考虑同一个 $SCC$ 里面的点见的转移）

然后考虑 $INF$ 的情况。

显然，如果从 $s$ 不能到达 $t$ ，那么显然答案为 $INF$ 。

还有一种情况，如果存在一个不为 $t$ 的点，从 $s$ 出发后，可以到达，但是没有出边，这种情况下如果走到了这个点，就不能继续走了，无法到达 $t$ ，答案为 $INF$ 。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res;
}
const int MAXN = 1e4+5,M = 1e6+5;
int n,m,s,t,u,v,head[MAXN],num_edge,id[MAXN];
double ans[MAXN],deg[MAXN],E[MAXN],val[105][105],epts=1e-7;
vector<int> G1[MAXN],G2[MAXN],G[MAXN];
il add_edge(int u,int v){G1[u].push_back(v);}
il add(int u,int v){G2[u].push_back(v),++deg[v];}
int dfn[MAXN],low[MAXN],bl[MAXN],stk[MAXN],top,cnt,num;
char in[MAXN];
il Tarjan(int u){
	dfn[u]=low[u]=++cnt,stk[++top]=u,in[u]=1;
	for(ri i=0;i<(int)G1[u].size();++i){
		int v=G1[u][i];
		if(!dfn[v]) Tarjan(v),low[u]=min(low[u],low[v]);
		else if(in[v]) low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u]){
		int y=0,tot=0;++num;
		do{
			y=stk[top--],in[y]=0,id[y]=++tot;
			bl[y]=num,G[num].push_back(y);
		}while(y^u);
	}
}
il Gauss(int s){
	for(ri i=1;i<=s;++i){
		int mx=i;
		for(ri j=i+1;j<=s;++j)
			if(fabs(val[j][i])>fabs(val[mx][i]))
				mx=j;
		if(mx^i) swap(val[i],val[mx]);
		if(fabs(val[i][i])<epts) continue;
		for(ri j=1;j<=s;++j) if(i^j){
			double div=val[j][i]/val[i][i];
			for(ri k=i+1;k<=s+1;++k)
				val[j][k]-=val[i][k]*div;
		}
	}
	for(ri i=1;i<=s;++i)
		ans[i]=val[i][s+1]/val[i][i];
}
int in_deg[MAXN];
il topo(){
	queue<int> q;q.push(bl[t]);
	for(ri i=1;i<=n;++i)
		for(ri j=0;j<(int)G2[i].size();++j)
			if(bl[i]^bl[G2[i][j]]) ++in_deg[bl[G2[i][j]]];
	while(!q.empty()){
		int pos=q.front(),s=G[pos].size();q.pop();
		for(ri i=1;i<=s;++i)
			for(ri j=1;j<=s+1;++j)
				val[i][j]=0;
		for(ri i=1;i<=s;++i){
			int u=G[pos][i-1];
			val[i][i]=1,val[i][s+1]=E[u];
			if(u==t) continue;
			for(int j=0;j<(int)G1[u].size();++j){
				int v=G1[u][j];
				if(bl[u]^bl[v]) continue;
				val[i][s+1]+=deg[u];
				val[i][id[v]]-=deg[u];
			}
		}
		Gauss(s);
		for(ri i=1;i<=s;++i){
			int u=G[pos][i-1];
			E[u]=ans[i];
			for(ri j=0;j<(int)G2[u].size();++j){
				int v=G2[u][j];
				if(bl[u]==bl[v]) continue;
				if(!(--in_deg[bl[v]])) q.push(bl[v]);
				E[v]+=(E[u]+1)*deg[v];
			}
		}
	}
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(n),read(m),read(s),read(t);
	for(ri i=1;i<=m;++i)
		read(u),read(v),add_edge(u,v),add(v,u);
	Tarjan(s);
	for(ri i=1;i<=n;++i){
		if(i^t){
			if(dfn[i]&&!deg[i]) return puts("INF"),0;
			if(deg[i]) deg[i]=1./deg[i];
		}
		else if(!dfn[i]) return puts("INF"),0;
	}
	topo();
	printf("%.3f ",E[s]);
	return 0;
}